Maximum flow relates to the problem of finding the maximum flow between sets of vertices in a directed graph. In one application, graphs may be used to model real world systems or designs and maximum flow may be used to determine or simulate operational characteristics of that application or design. A path is a list of vertices of a graph where each vertex has an edge, i.e. a connection between two vertices, from it to the next vertex. A weighted directed graph is a directed graph that has a weight, i.e. a numeric value, associated with each edge that may relate to the carrying capacity of the edge, e.g. the maximum flow that may be sent through the edge or vertex, as dictated by the application or design being modeled. A flow network is a weighted directed graph with two sets of specially marked nodes, the source “s” and the sink “t,” and a capacity function that maps edges to positive real numbers. A source is a vertex of a directed graph with no incoming edges and may represent a producer of data in an application or design. A sink is vertex of a directed graph with no outgoing edges and may represent a consumer of data in an application or design.
Applications of weighted directed graphs and maximum flow include modeling and analyzing shipping systems, airline scheduling systems, open pit mining operations, etc. Another application of maximum flow is image segmentation.
In image analysis, segmentation is the partitioning of a digital image into multiple regions (sets of pixels), according to a given criterion. The goal of segmentation is typically to locate objects of interest and is sometimes considered a computer vision problem. Unfortunately, many segmentation methods that are based only on local pixel information, and hence scalable for large graphs, are too simple to solve most problems. Other more advanced segmentation methods such as the traditional maximum flow method or model based method, provide the capability to segment based on information from a large capture range, but suffer from severe practical limitations for large graphs due to their large memory requirement and iterative traversal pattern. Many important segmentation algorithms are too simple to solve this problem accurately, compensating for this limitation with their predictability, generality, and efficiency.
Local Pixel Based Segmentation
A simple example of this kind of segmentation is thresholding a grayscale image with a fixed threshold t: each pixel p is assigned to one of two classes, P0 or P1, depending on whether I(p)<t or I(p)≧t. Threshold techniques, which make decisions based on local pixel information, are effective when the intensity levels of the objects fall squarely outside the range of levels in the background. When this assumption is not true, however, which is the case in most real world problems, the result is seldom acceptable.
Traditional maximum flow segmentation method can be applied on a down sampled version of a large graph. In fact, this is often the practice where maximum flow segmentation is needed on large graphs. This, however, does not yield a high quality segmentation results as information is lost in the process of re-sampling the large graph to a smaller version of it.
Accordingly, an effective, scalable, and efficient maximum flow segmentation method is needed.